package com.sicheng.lc.周赛.分类.dp.数位;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/18 22:05
 */
public class 最大为N的数字组合 {
    //https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/
    static int N = 10;
    static int[][] dp = new int[N + 1][N];

    {
        for (int[] ints : dp) {
            Arrays.fill(ints, 0);
        }
    }

    int parse(String d) {
        return d.charAt(0) - '0';
    }

    void init(String[] digits) {
        for (String d : digits) {
            dp[1][parse(d)] = 1;
        }
        for (int i = 2; i <= N; i++) {
            for (String digit : digits) {
                int x = parse(digit);
                for (String s : digits) {
                    int y = parse(s);
                    dp[i][x] += dp[i - 1][y];
                }
            }
        }
    }

    boolean contains(int x, String[] dgt) {
        for (String s : dgt) {
            if (parse(s) == x) {
                return true;
            }
        }
        return false;
    }

    private int dp(String[] digits, int n) {
        init(digits);
        ArrayList<Integer> nums = new ArrayList<>();
        while (n != 0) {
            nums.add(n % 10);
            n /= 10;
        }

        int res = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums.get(i);
            for (String d : digits) {
                int j = parse(d);
                if (j >= x)
                    break;
                res += dp[i + 1][j];

            }
            if (!contains(x, digits))
                break;
            if (i == 0)
                res++;
        }
        for (int i = 1; i < nums.size(); i++) {
            for (String d : digits) {
                int j = parse(d);
                res += dp[i][j];
            }
        }
        return res;
    }


    public int atMostNGivenDigitSet(String[] digits, int n) {
        return f(digits, n);
    }

    // 由于没有数位的限制条件 直接排列数即可
    static int[] pow = new int[N + 1];
    static {
        pow[0] = 1;
    }

    int f(String[] digits, int n) {

        ArrayList<Integer> nums = new ArrayList<>(10);
        while (n != 0) {
            nums.add(n % 10);
            n /= 10;
        }
        ArrayList<Integer> dgt = new ArrayList<>(10);
        for (String d : digits) {
            dgt.add(d.charAt(0) - '0');
        }
        for (int i = 1; i <= N; i++) {
            pow[i] = pow[i - 1] * dgt.size();
        }
        int res = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums.get(i);
            for (int j : dgt) {
                if (j >= x)
                    break;
                res += pow[i];
            }

            if (!dgt.contains(x))
                break;

            if (i == 0)
                res++;

        }
        //特判 处理有前导
        for (int i = 1; i < nums.size(); i++) {
            res += pow[i];
        }
        return res;
    }

    public static void main(String[] args) {
        最大为N的数字组合 s = new 最大为N的数字组合();
        String[] d = {"1", "3", "5", "7"};
        int n = 100;
        System.out.println(s.atMostNGivenDigitSet(d, n));
    }
}
